package day4;

/**
 * 
 * 问题描述：
 * 逆序对问题：在一个数组中，左边的数如果比右边的数大，则这两个数
 * 构成一个逆序对，请打印逆序对
 * 
 * 解题思路：
 * 使用归并排序的思路处理
 */
public class ReverseOrder {
    public static int calculateReverse(int[] array) {
        if (array == null || array.length < 2) {
            return 0;
        }
        return process(array, 0, array.length - 1);
    }

    private static int process(int[] array, int left, int right) {
        if (left == right) {
            return 0;
        }

        int middle = left + ((right - left) >> 1);
        return process(array, left, middle)+ process(array, middle + 1, right)+ merge(array, left, middle, right);
    }

    private static int merge(int[] array, int left, int middle, int right) {
        int[] temp = new int[right - left + 1];
        int tempIndex = 0;
        int pLeft = left;
        int pRight = middle + 1;
        int result=0;

        while (pLeft <= middle && pRight <= right) {
            //因为左边，右边两侧已有序，因此如果左边当前这个数大于右边，那么左边从这个数起的所有数都大于右边
           result+= array[pLeft] <= array[pRight]?0:middle-pLeft+1;
           temp[tempIndex++]=array[pLeft] <= array[pRight]?array[pLeft++]:array[pRight++]; 
        }

        while (pLeft<=middle) {
            temp[tempIndex++]=array[pLeft++];
        }
        while (pRight<=right) {
            temp[tempIndex++]=array[pRight++];
        }
        for (int i = 0; i < temp.length; i++) {
            array[left+i]=temp[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] test=new int[]{5,2,3,7,3,6};//5,2 5,3 5,4 7,4 7,6
        System.out.println(calculateReverse(test));
    }
}
